Day22 - Crypto 0x2 古典

前言

• 今天開始來介紹古典密碼學，古典密碼學大部分都是利用替換式密碼或移項式密碼，還有加上古人的各種創意，所打造出不同的加密方式

凱薩密碼(Caesar cipher)

• 古典密碼學中最知名的加密方式，利用替換加密
• 作法
  • 將要加密的字串中的英文字母，每個位置都往後n個字母
    • 也就是說A=>D, B=>E, X=>A....
• example (key = 3)
  • 原文: ABCDEFGHIJKLMNOPQRSTUVWXYZ
  • 密文: DEFGHIJKLMNOPQRSTUVWXYZABC
• 示意圖
  • 
• 圖片參考自: https://www.geeksforgeeks.org/caesar-cipher-in-cryptography/

如何破解

• 直接使用暴力破解，key從1嘗試到26，接著可以搭配詞頻分析，與常見的單字比較，藉此猜出哪個語法最合理與最像明文
• 也可以透過字頻分析，透過常出現的單字與字推出明文
• 線上爆破工具：http://theblob.org/rot.cgi
• 字頻分析工具：https://quipqiup.com/

ROT13

• rotate by 13 places
• 凱薩加密的key = 13的狀態，剛好會對應到26個字母的一半
  • 有個特殊的特性，就是自己ROT13再ROT13一次會剛好是自己
  • 密碼學上會稱為「對等加密」
• 示意圖
  • 
  • HELLO => URYYB => HELLO
• 圖片參考自: https://zh.wikipedia.org/zh-tw/ROT13

ROT47

• 除了字母以外，將符號以及數字全部納入，除了空白以外，將ASCII字元中的!(33) - ~(126)都被納入47位做循環
• example
  • Halloworld => w2==@H@C=5

維吉尼亞密碼

• 透過查表來進行字母的轉換，仔細觀察一下，他其實也是凱薩密碼的變形
  • 第一行就是凱薩加密key=0
  • 第二行則是凱薩加密key=1
  • 第二行則是凱薩加密key=2
  • 以此類推...

如何加密

• 明文：HELLO
• 決定密鑰：JKLMN
  • 查表進行加密，紅色為明文、藍色為密鑰
• 密文：QOWXB

解密

• 密鑰：JKLMN
• 密文：QOWXB
  • 藍色部分往下查找，往左對應即可知道密文
• 明文：HELLO

如何破解 - 卡西斯基試驗 (Kasiski examination)

• 基於the這樣的常用的單字的特性

  • 很有可能碰到同樣的密鑰字母加密，也就使密文中出現相同的內容

• 密鑰相同的情況下，因為有重複的段落，藉此可猜出密鑰的長度

  • 明文: CRYPTO IS SHORT FOR CRYPTOGRAPHY
  • 密鑰: ABCDAB CD ABCDA BCD ABCDABCDABCD
  • 密文: CSASTP KV SIQUT GQU CSASTPIUAQJB

• 若有密文有兩段重複的地方，就有機會破譯出密鑰的長度

  • DYDUXRMHTVDVNQDQNWDYDUXRMHARTJGWNQD
    • DYDUXRMH距離下一次出現的長度為16，藉此可以推理出密鑰長度為16的因數，1,2,4,8,16
    • NQD則距離20個字母，代表密鑰長度有機會為20,10,5,4,2
    • 取兩個的交集，可以推測出密鑰長度為2

密碼棒

• 把字條纏在木棒上，橫向寫下想傳送的訊息，解密在用相同的木棒纏繞
  • 

豬圈密碼

• 以格子為基礎的簡單替代式密碼。即使使用符號，也不會影響密碼分析
• 也稱為共濟會密碼，因為早期共濟會常用這種密碼保護訊息
• 示意圖
  • 
• example
  • ABCDEFG
  • 

線上轉換器：http://ctf.ssleye.com/yd_pigpen.html?text=ABCDEFG

古典密碼學的問題

• 柯克霍夫原則（Kerckhoffs’ principle）
  • 即使密碼系統細節中的演算法眾所皆知，只要key不被洩漏，密文就是安全的
  • 但古典密碼學大部分都已經被破解，畢竟經過多年的疊代，以及數學家的腦力激盪，古典密碼學已經不敷使用，不過這也奠定了現代密碼學的基礎

Ref

• https://www.geeksforgeeks.org/caesar-cipher-in-cryptography/
• https://zh.wikipedia.org/zh-tw/%E7%BB%B4%E5%90%89%E5%B0%BC%E4%BA%9A%E5%AF%86%E7%A0%81
• https://zhuanlan.zhihu.com/p/111611977
• https://hitcon.org/2018/CMT/slide-files/d1_s2_r4.pdf
• https://medium.com/@yellowgirl3614/%E5%AF%86%E7%A2%BC%E5%AD%B8-%E4%B8%80-%E5%8F%A4%E5%85%B8%E5%AF%86%E7%A2%BC%E5%AD%B8-455e43038241